#include <iostream>
#include <queue>
using namespace std;

/*
    TreeNode作为二叉树的单位节点
    有一个存储数据，一个左节点的位置和一个右节点的位置

*/
typedef struct TreeNode{

}TreeNode;


/*
    BinaryTree二叉树 
    主要是一个根节点 
    可以用值来构造申请内存
    可以没有值 
*/
class BinaryTree{

    //析构函数 释放空间即可
    
    
    /*
        获取根节点，直接返回就行
    */
    TreeNode* getNode();
    /*
        判断是否为空的函数 
        即 根节点是否为空
    */
   bool isEmpty();

    /*
        insert 先创建一个新节点
        如果树 空，那就让根节点 = 新节点，返回即可
        如果树 不空  
            创建一个由树节点构成的队列，把根节点推入 队
            当队列不空的时候，当前节点为队列最前面的节点。然后出队
            如果左子树为空那 左节点为新节点 
            右子树为空 右节点为新节点。否则就当前的左节点和右节点都推入队列
    */
   void insert(int data);

   // 树的遍历有三种递归遍历和一种非递归层序遍历
   /*
        三种递归遍历分别有三种顺序
        前序  简称 根左右 从根节点开始先左子树然后到右子树
        中序  简称 左根右 从左子树到根节点最后回到右节点
        后序      左右根  从左子树到右子树最后到根节点
   */ 
   /*
        前序遍历  
        如果根节点空直接返回
        不空 先输出存储的数值 
            递归调用左子树
            递归调用右子树
   */
    void preorderedTraversal(TreeNode* newNode)const;

    /*
        中序遍历
        同理 空直接返回
        不空 先递归左
            输出
            递归右
    */
    void inorderedTraversal(TreeNode* newNode)const;

    /*
        后序遍历
        空 返回 
        不空 递归左
            递归右
            输出
    */
    void postorderedTraversal(TreeNode* newNode)const;

    // 层序遍历 优先每一层遍历完之后继续遍历
    /*
        由树节点构成一个队列，先把根节点推进去。
        当队列不空的情况下 创建一个当前节点为队列的头部节点
        然后出队。输出数据。
        如果左节点不为空 就把左推进队列。
        如果右节点不为空 就把右推进队列。
    */
    void levelorderTraversal();

    /*
        高度。如果节点为空 返回0  
        节点不为空 
            左边的高度 递归调用左子树 
            右边高度  同理递归右子树 
            最后 左右高度最大值+1
    */
    int height(TreeNode* node)const;

    /*
        如果空 返回 0
        不空 返回 1+递归左子树+递归右子树
    */
    int countNode(TreeNode* node)const;

    /*
        空 返回 false 
        如果找到 true 
        返回 递归左 || 递归右
    */
    bool search(TreeNode* node,int value) const;

};


int main(){
    
}